package sort;


/**
 * 选择排序使用了线性查找来寻找最小值，因此在第 1 轮中需要比较 n -1 个数字，第
 * 2 轮需要比较 n -2 个数字……到第 n -1 轮的时候就只需比较 1 个数字了。因此，总的比
 * 较次数与冒泡排序的相同，都是 (n-1)+(n-2)+…+1 ≈ n²/2 次。
 * 每轮中交换数字的次数最多为 1 次。如果输入数据就是按从小到大的顺序排列的，
 * 便不需要进行任何交换。选择排序的时间复杂度也和冒泡排序的一样，都为 O(n²)。
 */
public class Selection implements Sortable {
    @Override
    public void sort(int[] arr) {
        for (int i=0; i<arr.length; i++) {
            int temp = arr[i];
            int tempL = i;
            for (int j=i+1; j<arr.length; j++) {
                if (temp > arr[j]) {
                    temp = arr[j];
                    tempL = j;
                }
            }
            arr[tempL] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        System.out.println("before sort ");
        ArrayData.printArr();
        new Selection().sort(ArrayData.ARR);
        System.out.println("after sort ");
        ArrayData.printArr();
    }

}
